---@coding utf8

---@breif 搜索插入位置
---@param tab any[]
---@param x any
---@param asc boolean|nil: true为升序，false为降序
local function bisect_right(tab, x, asc)
    local cur_size = #tab
    if cur_size <= 0 then
        return 1
    end
    local lo = 1
    local hi = cur_size + 1
    while lo < hi do
        local mid_pos = (lo + hi) // 2
        if x < tab[mid_pos] then
            hi = mid_pos
        else
            lo = mid_pos + 1
        end
    end
    return lo
end


--[[  测试用例
function dump_table_list(tab)
    for _, value in ipairs(tab) do
        print(value)
    end
end

function test_bisert(tab, value)
    local idx = bisect_right(tab, value)
    print(idx)
    return idx
end

function assert(ret)
    if ret == true then
        return
    end
    local dinfo = debug.getinfo(2, "Sln")
    print(dinfo.source , dinfo.currentline)
end

--assert(false)

assert(test_bisert({}, 0) == 1)
assert(test_bisert({}, 1) == 1)
assert(test_bisert({}, -1) == 1)

assert(test_bisert({-1}, 0) == 2)
assert(test_bisert({-1}, -1) == 2)
assert(test_bisert({-1}, -2) == 1)

assert(test_bisert({0}, -1) == 1)
assert(test_bisert({0}, 0) == 2)
assert(test_bisert({0}, 1) == 2)

assert(test_bisert({1,3,6}, 0) == 1)
assert(test_bisert({1,3,6}, 1) == 2)
assert(test_bisert({1,3,6}, 2) == 2)
assert(test_bisert({1,3,6}, 3) == 3)
assert(test_bisert({1,3,6}, 4) == 3)
assert(test_bisert({1,3,6}, 5) == 3)
assert(test_bisert({1,3,6}, 6) == 4)
assert(test_bisert({1,3,6}, 7) == 4)
--]]
